# -*- coding: utf-8 -*-

"""剑指 Offer II 089. 房屋偷盗
一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响小偷偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组 nums ，请计算 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：
输入：nums = [1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：
输入：nums = [2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示：
1 <= nums.length <= 100
0 <= nums[i] <= 400"""

class Solution:
    """从第i位置开始偷，
        如果偷了i，那么又从第i+2的位置开始偷的最高金额
        如果没有偷i，偷了第i+1，那么又从第i+3的位置开始偷的最大金额
        用动态规划；
        上下回是重复操作，且有依赖关系，用递归"""
    def rob(self, nums):
        last = len(nums)-1
        if last == 0:
            return nums[0]
        elif last == 1:
            return max(nums[0], nums[1])
        elif last == 2:
            return max(nums[last-2]+nums[last], nums[last-1])

        table = {
            last-2: max(nums[last-2]+nums[last], nums[last-1]),
            last-1: max(nums[last-1], nums[last]),
            last: nums[last]
            }
        def optimal(i):
            if i in (last-2, last-1, last):
                return table[i]
            
            if i+3 in table:
                forth = table[i+3]
            else:
                forth = optimal(i+3)
                table[i+3] = forth
            
            if i+2 in table:
                third = table[i+2]
            else:
                third = optimal(i+2)
                table[i+2] = third

            return max(nums[i]+third, nums[i+1]+forth)
        return optimal(0)


if __name__ == '__main__':
    so = Solution()
    print(so.rob([1,2,3,1]))
    print(so.rob([2,7,9,3,1]))
    print(so.rob([1,1,3,6,7,10,7,1,8,5,9,1,4,4,3]))
    
